# Q: find the longest palindrome in the following 1169-character string:
#
# Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
# inentanewnationconceivedinzLibertyanddedicatedtotheproposit
# ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
# rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
# atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
# avecometodedicpateaportionofthatfieldasafinalrestingplacefo
# rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
# etherfangandproperthatweshoulddothisButinalargersensewecann
# otdedicatewecannotconsecratewecannothallowthisgroundThebrav
# elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove
# ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl
# ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
# tisforusthelivingrathertobededicatedheretotheulnfinishedwor
# kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather
# forustobeherededicatedtothegreattdafskremainingbeforeusthat
# fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh
# ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
# olvethatthesedeadshallnothavediedinvainthatthisnationunsder
# Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
# ythepeopleforthepeopleshallnotperishfromtheearth
#
# A: The algorithm below walk the string only once thus taking O(n). While
# walking, it keep track a marker along with it. As soon as it start seeing
# mirror of characters (e.g. i == marker or i = marker-2), it will put marker. As going
# along further, if will keep checking and push marker further back until no
# more mirrorred characters found. This indicate a palindrome. Then it compared
# to previous recorded palindrome, if any. If it's longer, then update the
# tracked longest palindrome.

def longest_palindrome(thestr):
   start = stop = 0
   currentStart = 0
   for i in range(len(thestr)):
      if currentStart-1 >= 0 and thestr[i] == thestr[currentStart-1]:
         currentStart -= 1
      elif thestr[i] == thestr[currentStart]:
         pass
      elif i-currentStart > 1 and i-currentStart > stop-start:
         start, stop = currentStart, i
         currentStart = i + 1
      else:
         currentStart = i
   return thestr[start:stop]


data = ''.join("""
Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
inentanewnationconceivedinzLibertyanddedicatedtotheproposit
ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
avecometodedicpateaportionofthatfieldasafinalrestingplacefo
rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
etherfangandproperthatweshoulddothisButinalargersensewecann
otdedicatewecannotconsecratewecannothallowthisgroundThebrav
elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove
ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl
ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
tisforusthelivingrathertobededicatedheretotheulnfinishedwor
kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather
forustobeherededicatedtothegreattdafskremainingbeforeusthat
fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh
ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
olvethatthesedeadshallnothavediedinvainthatthisnationunsder
Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
ythepeopleforthepeopleshallnotperishfromtheearth
""".strip().split())

print(longest_palindrome(data))

